﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using KLadderProposal.Interfaces;
using KLadderProposal.Interfaces.BasicStructures;

namespace KLadderProposal.Algorithms
{
    public class Clique4Algorithm : IAlgorithm
    {
        #region Fields (1)

        private const int NeighborThreshhold = 2;

        #endregion Fields

        #region Properties (2)

        public int CliqueSize
        {
            get;
            set;
        }

        public double Treshold
        {
            get;
            set;
        }



        #endregion Properties

        #region Methods (13)

        // Public Methods (1) 

        //stage1 find 4cliqe
        //stage2 ExpandCluster by 4 and 4
        //stage3 traverse through all neighbores of the clique members and find  neighbore that connect to 3 nodes in clique
        //stage4 traverse through all neighbores with common nodes and add it to clique
        //if stage 2 or 3 find new nodes so add the new node to clique and repet 2 and 3 stage untill no more nodes added
        //stage5 find next 4 clique and so on
        public void Run(IGraph graph)
        {
            DateTime dt = DateTime.Now;

            List<SortedDictionary<string, GraphNode>> clique3List = Find3Clique(graph.Nodes);
            SortedDictionary<string, SortedDictionary<string, GraphNode>> clique4List = null;
            SortedDictionary<string, SortedDictionary<string, GraphNode>> clique5List;
            SortedDictionary<string, SortedDictionary<string, GraphNode>> clique6List;
            SortedDictionary<string, SortedDictionary<string, GraphNode>> clique7List;
            //SortedDictionary<string, SortedDictionary<string, GraphNode>> clique8List;
            //SortedDictionary<string, SortedDictionary<string, GraphNode>> clique9List;
            //SortedDictionary<string, SortedDictionary<string, GraphNode>> clique10List;
            clique4List = FindBiggerClique(graph, clique3List, 4);

            //for (int i = 4; i <= CliqueSize; i++)
            //{
            //    clique4List = FindBiggerClique(graph, clique4List.Values, i);
            //}

            clique5List = FindBiggerClique(graph, clique4List.Values, 5);
            clique6List = FindBiggerClique(graph, clique5List.Values, 6);
            clique7List = FindBiggerClique(graph, clique6List.Values, 7);
            //clique8List = FindBiggerClique(graph, clique7List.Values, 8);
            //clique9List = FindBiggerClique(graph, clique8List.Values, 9);
            //clique10List = FindBiggerClique(graph, clique9List.Values, 10);

            int clusterNumber = 1;
            int count = clique7List.Count;
            int progress = 1;
            int cliqueSize = CliqueSize;
            foreach (KeyValuePair<string, SortedDictionary<string, GraphNode>> clique in clique7List)
            {
                int j = 0;
                foreach (KeyValuePair<string, GraphNode> node in clique.Value)
                {
                    if (!node.Value.IsMarkedAsDeleted)
                        j++;

                }

                if (j >= cliqueSize)
                {
                    foreach (KeyValuePair<string, GraphNode> node in clique.Value)
                    {
                        node.Value.IsMarkedAsDeleted = true;
                        node.Value.ClusterNumber = clusterNumber;
                    }

                    while (ExpendClique(clusterNumber, clique.Value, cliqueSize))
                    {
                        // ExpendClique(clusterNumber, clique.Value, cliqueSize);

                    }
                    clusterNumber++;
                }


                clusterNumber++;
                ReportProgressExpand((float)progress++ / count);
            }

            Console.WriteLine(DateTime.Now - dt);
        }
        // Private Methods (12) 

        private void AddNodeToBiggerCluster(int size, SortedDictionary<string, GraphNode> cliqueNodes, GraphNode item,
                                            SortedDictionary<string, SortedDictionary<string, GraphNode>> list2)
        {
            var dict = new SortedDictionary<string, GraphNode>();
            var stamp = new int[size];
            int index = 0;

            foreach (var item2 in cliqueNodes)
            {
                stamp[index] = item2.Value.SequenceNumber;
                dict.Add(item2.Key, item2.Value);
                index++;
                //item2.Value.IsMarkedAsDeleted = true;
                //item2.Value.ClusterNumber = clusterNumber;
            }

            stamp[index] = item.SequenceNumber;
            dict.Add(item.Label, item);
            //item.IsMarkedAsDeleted = true;
            // item.ClusterNumber = clusterNumber;
            Array.Sort(stamp);
            string key = string.Join(",", stamp);

            if (list2.ContainsKey(key)) //make sure that  duplicate clique not added
            {
                if (FindCommonItems(list2[key], dict).Count > size - 1)
                    return;
            }
            list2.Add(key, dict);
            // clusterNumber++;
        }

        private bool Contains(SortedList<string, GraphNode> list1, SortedDictionary<string, GraphNode> list2)
        {
            if (FindCommonItems(list1, list2).Count > Treshold)
                return true;
            return false;
        }

        private bool ExpendClique(int i, SortedDictionary<string, GraphNode> clique, int cliqueSize)
        {
            SortedDictionary<string, GraphNode> addedValues = new SortedDictionary<string, GraphNode>();
            int localCliqueSize = cliqueSize - 1;// (int)(clique.Count * _factor);
            bool nodedAdded = false;
            foreach (KeyValuePair<string, GraphNode> node in clique)
            {
                foreach (var neighbor in node.Value.Neighbors)
                {
                    if (neighbor.Value.IsMarkedAsDeleted)
                        continue;
                    SortedList<string, GraphNode> list = FindCommonItems(node.Value.Neighbors,
                        neighbor.Value.Neighbors, cliqueSize);
                    if (list.Count > localCliqueSize)
                    {
                        foreach (KeyValuePair<string, GraphNode> keyValuePair in list)
                        {
                            if (!addedValues.ContainsKey(keyValuePair.Key))
                            {
                                addedValues.Add(keyValuePair.Key, keyValuePair.Value);
                                keyValuePair.Value.IsMarkedAsDeleted = true;
                                keyValuePair.Value.ClusterNumber = i;
                            }
                        }
                        nodedAdded = true;
                    }
                }
            }

            //find 2 nodes that connected to three 
            //foreach (KeyValuePair<string, GraphNode> node in clique)
            //{
            //    foreach (var neighbor1 in node.Value.Neighbors)
            //    {
            //        foreach (var neighbor2 in node.Value.Neighbors)
            //        {
            //            if (neighbor1.Value.IsMarkedAsDeleted ||
            //                neighbor2.Value.IsMarkedAsDeleted)
            //                continue;
            //            if (!neighbor1.Value.Neighbors.Contains(neighbor2))
            //                continue;
            //            SortedList<string, GraphNode> list1 = FindCommonItems(neighbor1.Value.Neighbors,
            //                                                                  neighbor2.Value.Neighbors, 3);

            //            if (list1.Count > localCliqueSize)
            //            {
            //                if (!addedValues.ContainsKey(neighbor1.Key) &&
            //                    !addedValues.ContainsKey(neighbor2.Key))
            //                {
            //                    addedValues.Add(neighbor1.Key, neighbor1.Value);
            //                    neighbor1.Value.IsMarkedAsDeleted = true;
            //                    neighbor1.Value.ClusterNumber = i;
            //                    addedValues.Add(neighbor2.Key, neighbor2.Value);
            //                    neighbor2.Value.IsMarkedAsDeleted = true;
            //                    neighbor2.Value.ClusterNumber = i;
            //                    nodedAdded = true;

            //                }
            //            }
            //        }
            //    }
            //}

            if (nodedAdded)
            {
                foreach (KeyValuePair<string, GraphNode> keyValuePair in addedValues)
                {
                    clique.Add(keyValuePair.Key, keyValuePair.Value);
                }
            }
            return nodedAdded;
        }

        private List<SortedDictionary<string, GraphNode>> Find3Clique(IEnumerable<GraphNode> graph)
        {
            var lists = new List<SortedDictionary<string, GraphNode>>();
            int cliqueSequnceNumber = 0;
            int count = 0;
            int sum = graph.Count();

            foreach (GraphNode root in graph)
            {
                if (root.ThreeCliqueNumber != 0)
                    continue;
                foreach (var neighbor in root.Neighbors)
                {
                    if (neighbor.Value.ThreeCliqueNumber != 0)
                        continue;
                    SortedList<string, GraphNode> list = FindCommonItems(root.Neighbors, neighbor.Value.Neighbors);
                    foreach (var item in list)
                    {
                        if (item.Value.ThreeCliqueNumber != 0)
                            continue;
                        cliqueSequnceNumber++;

                        var dic = new SortedDictionary<string, GraphNode>();
                        if (root.Label == neighbor.Key || root.Label == item.Key || neighbor.Key == item.Key) continue;

                        cliqueSequnceNumber++;
                        dic.Add(root.Label, root);
                        dic.Add(neighbor.Key, neighbor.Value);
                        dic.Add(item.Key, item.Value);

                        root.ThreeCliqueNumber = cliqueSequnceNumber;
                        neighbor.Value.ThreeCliqueNumber = cliqueSequnceNumber;
                        item.Value.ThreeCliqueNumber = cliqueSequnceNumber;

                        lists.Add(dic);
                    }
                }
                count++;
                ReportProgressFind3Clique((float)sum / count);
            }
            return lists;
        }

        private SortedDictionary<string, SortedDictionary<string, GraphNode>>
          FindBiggerClique(IGraph graph, IEnumerable<SortedDictionary<string, GraphNode>> clique, int size)
        {
            var list2 = new SortedDictionary<string, SortedDictionary<string, GraphNode>>();
            int count = 0;
            int sum = clique.Count();
            float progrees;
            //  int clusterNumber = 0;
            foreach (var cliqueNodes in clique)
            {
                foreach (GraphNode item in graph.Nodes)
                {
                    if (item.IsMarkedAsDeleted)
                        continue;
                    if (cliqueNodes.ContainsKey(item.Label))
                        continue;
                    if (!Contains(item.Neighbors, cliqueNodes)) continue;

                    AddNodeToBiggerCluster(size, cliqueNodes, item, list2);
                    break;
                }
                count++;
                progrees = (float)count / sum;
                ReportprogressFind4Clique(progrees);
            }
            return list2;
        }

        private Dictionary<string, GraphNode> FindCommonItems(SortedDictionary<string, GraphNode> sortedList1,
                                                              IDictionary<string, GraphNode> sortedList2)
        {
            var nodes = new Dictionary<string, GraphNode>();
            foreach (var item in sortedList1)
            {
                if (sortedList2.ContainsKey(item.Key))
                {
                    nodes.Add(item.Key, item.Value);
                }
            }
            return nodes;
        }

        private Dictionary<string, GraphNode> FindCommonItems(SortedList<string, GraphNode> sortedList1,
                                                              IDictionary<string, GraphNode> sortedList2)
        {
            var nodes = new Dictionary<string, GraphNode>();
            foreach (var item in sortedList1)
            {
                if (sortedList2.ContainsKey(item.Key))
                {
                    nodes.Add(item.Key, item.Value);
                }
            }
            return nodes;
        }

        private SortedList<string, GraphNode> FindCommonItems(SortedList<string, GraphNode> sortedList1,
                                                              SortedList<string, GraphNode> sortedList2)
        {
            var nodes = new SortedList<string, GraphNode>();
            foreach (var item in sortedList1)
            {
                if (sortedList2.ContainsKey(item.Key)) //&& item.Value.ThreeCliqueNumber != 0)
                {
                    nodes.Add(item.Key, item.Value);
                }
            }
            return nodes;
        }

        private SortedList<string, GraphNode> FindCommonItems(SortedList<string, GraphNode> sortedList1,
                                                             SortedList<string, GraphNode> sortedList2,
            int tresholed)
        {
            var nodes = new SortedList<string, GraphNode>();
            int i = 0;
            foreach (var item in sortedList1)
            {
                if (sortedList2.ContainsKey(item.Key) &&
                    !item.Value.IsMarkedAsDeleted)
                {
                    nodes.Add(item.Key, item.Value);
                    i++;
                    if (i >= tresholed)
                        return nodes;
                }
            }
            return nodes;
        }

        private void ReportProgressExpand(float count)
        {
            Console.WriteLine("Clique Progress {0} ", count);
        }

        //private bool Find4CliqueAlternative(IGraph graph)
        //{
        //    bool clique4Found = false;
        //    var commonNeigbors = new List<GraphNode>();

        //    int maxNeigborsCount = graph.Nodes.Max(node => node.Neighbors.Count);
        //    GraphNode nodeWithMaxNeigbors = graph.Nodes.Where(node => node.Neighbors.Count == maxNeigborsCount).First();

        //    foreach (GraphNode node in graph.Nodes)
        //    {
        //        if (node == nodeWithMaxNeigbors)
        //            continue;

        //        commonNeigbors = new List<GraphNode>();
        //        if (GetCommonNeigborsCount(node, nodeWithMaxNeigbors, commonNeigbors) <= 3) continue;
        //        foreach (GraphNode commonNeigbor in commonNeigbors)
        //        {
        //            foreach (GraphNode node1 in commonNeigbors)
        //            {
        //                if (commonNeigbor == node1)
        //                    continue;
        //                foreach (GraphNode node2 in commonNeigbors)
        //                {
        //                    if (node2 == node1 || node2 == commonNeigbor)
        //                        continue;
        //                    foreach (GraphNode node3 in commonNeigbors)
        //                    {
        //                        if (node3 == node1 || node3 == commonNeigbor || node3 == node2)
        //                            continue;
        //                        if (UtilesIsNeighbors(commonNeigbor, node2, node3, node1))
        //                        {
        //                            clique4Found = true; ///commonNeigbor, node2, node3, node1 are the CLIQUE (hope)
        //                            return true;
        //                        }
        //                    }
        //                }
        //            }
        //        }
        //    }

        //    if (clique4Found == false)
        //    {
        //        foreach (GraphNode node in graph.Nodes)
        //        {
        //            foreach (GraphNode node0 in graph.Nodes)
        //            {
        //                if (node == node0)
        //                    continue;

        //                if (GetCommonNeigborsCount(node, node0, commonNeigbors) > 3)
        //                {
        //                    //to add 4 loop..!!!
        //                }
        //            }
        //        }
        //    }

        //    return clique4Found;
        //}
        //private bool FindNewNeighbors(KeyValuePair<string, GraphNode> neighbor,
        //                              SortedDictionary<string, GraphNode> dictionary)
        //{
        //    foreach (var keyValuePair in dictionary)
        //    {
        //        if (neighbor.Key == keyValuePair.Key)
        //            return false;
        //    }
        //    {
        //        Dictionary<string, GraphNode> findCommonItems = FindCommonItems(neighbor.Value.Neighbors, dictionary);
        //        if (findCommonItems.Count > NeighborThreshhold)
        //        {
        //            return true;
        //        }
        //    }
        //    return false;
        //}
        //private bool Stage1Find4Clique1(IGraph graph, GraphNode node1, out GraphNode node2,
        //                                out GraphNode node3, out GraphNode node4)
        //{
        //    node2 = null;
        //    node3 = null;
        //    node4 = null;
        //    var histogram = new Histogram<GraphNode>();
        //    foreach (GraphNode inode2 in graph.Nodes) //pick node
        //    {
        //        //todo1 if node 2 is not neighbor of node 1 continue
        //        if (inode2.IsMarkedAsDeleted ||
        //            node1 == inode2 ||
        //            Stage1Containes(node1, inode2))
        //            continue;
        //    }
        //    foreach (GraphNode inode3 in graph.Nodes) //pick node
        //    {
        //        if (inode3.IsMarkedAsDeleted ||
        //            node1 == inode3 ||
        //            Stage1Containes(node1, inode3))
        //            continue;
        //    }
        //    foreach (GraphNode inode4 in graph.Nodes) //pick node
        //    {
        //        if (inode4.IsMarkedAsDeleted ||
        //            node1 == inode4 ||
        //            Stage1Containes(node1, inode4))
        //            continue;
        //    }
        //    //if (UtilesIsNeighbors(node1, inode2, inode3, inode4))
        //    //            {
        //    //                node2 = inode2;
        //    //                node3 = inode3;
        //    //                node4 = inode4;
        //    //                return true;
        //    //            }
        //    //        }
        //    //
        //    for (int i = 0; i < node1.Neighbors.Values.Count - 3; i++)
        //    {
        //        foreach (GraphNode i1 in node1.Neighbors.Values[0].Neighbors.Values)
        //        {
        //            histogram.IncrementCount(i1);
        //        }
        //        foreach (GraphNode i2 in node1.Neighbors.Values[1].Neighbors.Values)
        //        {
        //            histogram.IncrementCount(i2);
        //        }
        //        foreach (GraphNode i3 in node1.Neighbors.Values[2].Neighbors.Values)
        //        {
        //            histogram.IncrementCount(i3);
        //        }

        //        foreach (var u in histogram)
        //        {
        //            if (u.Value > 2)
        //            {
        //                node2 = node1.Neighbors.Values[0];
        //                node3 = node1.Neighbors.Values[1];
        //                node4 = node1.Neighbors.Values[2];
        //                return true;
        //            }
        //        }
        //    }
        //    return false;
        //
        //private bool Stage1Find4Clique(IGraph graph, GraphNode node1, out GraphNode node2,
        //                               out GraphNode node3, out GraphNode node4)
        //{
        //    node2 = node3 = node4 = null;
        //    foreach (GraphNode inode2 in graph.Nodes) //pick node
        //    {
        //        //todo2 if node 2 is not neighbor of node 1 continue
        //        if (inode2.IsMarkedAsDeleted)
        //            continue;
        //        foreach (GraphNode inode3 in graph.Nodes) //pick node
        //        {
        //            if (inode3.IsMarkedAsDeleted)
        //                continue;
        //            foreach (GraphNode inode4 in graph.Nodes) //pick node
        //            {
        //                if (inode4.IsMarkedAsDeleted)
        //                    continue;
        //                if (UtilesIsNeighbors(node1, inode2, inode3, inode4))
        //                {
        //                    node2 = inode2;
        //                    node3 = inode3;
        //                    node4 = inode4;
        //                    return true;
        //                }
        //            }
        //        }
        //    }
        //    return false;
        //}
        //try do it with bines
        //private List<GraphNode> Stage2AddNodeToClique1(List<GraphNode> clique)
        //{
        //    List<GraphNode> edgesInClique = new List<GraphNode>();

        //    //0,1,2,3-clique,  edge 4 connect to 0  1 and 2 ,edge 5 connect to 0 and 1
        //    foreach (GraphNode item in clique)//trevers 0,1,2,3
        //    {
        //        foreach (GraphNode item1 in item.Neighbors.Values)//trevers all clique Neighbors 
        //        {
        //            List<GraphNode> connectedCliqueEdges = new List<GraphNode>();//list of connected edges to the new edge

        //            HashSet<GraphNode> connectedCliqueEdges1 = new HashSet<GraphNode>();
        //            if (item1.IsMarkedAsDeleted)//if is mark to delete edge contain to same clique or diffrent clique
        //                continue;//

        //            foreach (GraphNode item2 in item1.Neighbors.Values)//at least find 3 edges in clique
        //            {
        //                if (UtilesIsInClique(clique, item2))
        //                    connectedCliqueEdges1.Add(item2);

        //                //change this function
        //                //  if (clique.Contains(item2))
        //                //    connectedCliqueEdges.Add(item2);
        //            }
        //            if (connectedCliqueEdges1.Count() > 2)
        //                edgesInClique.Add(item1);
        //            //connectedCliqueEdges = connectedCliqueEdges.Distinct().ToList();
        //            //if (connectedCliqueEdges.Count > 2)//if the new edge connected to at least 3 edges so it's new 4 clique
        //            //{
        //            //    edgesInClique.Add(item1);
        //            //}
        //        }
        //    }

        //    return edgesInClique.Distinct<GraphNode>().ToList<GraphNode>();
        //}
        // private void Stage2ExpandCluster(int clusterNumber, List<GraphNode> clique)
        //private int GetCommonNeigborsCount(GraphNode graphNode, GraphNode neighbor, List<GraphNode> commonNeigbors)
        //{
        //    //commonNeigbors.Add(graphNode);
        //    int commonNeighborsCount = 0;
        //    int i = 0, j = 0;

        //    while (i < graphNode.Neighbors.Count && j < neighbor.Neighbors.Count)
        //    {
        //        string label1 = graphNode.Neighbors.Values[i].Label;
        //        string label2 = neighbor.Neighbors.Values[j].Label;

        //        int comparisonResult = label1.CompareTo(label2);
        //        if (comparisonResult == 0)
        //        {
        //            commonNeighborsCount++;
        //            commonNeigbors.Add(neighbor.Neighbors.Values[j]);
        //            i++;
        //            j++;
        //        }
        //        else if (comparisonResult > 0)
        //            j++;
        //        else
        //            i++;
        //    }

        //    return commonNeighborsCount;
        //}
        //private bool IsNeighbors(GraphNode node1, GraphNode node2, GraphNode node3, GraphNode node4)
        //{
        //    bool findNode2 = false, findNode3 = false, findNode4 = false;
        //    if (node1 == node2 ||
        //        node1 == node3 ||
        //        node1 == node4 ||
        //        node2 == node3 ||
        //        node2 == node4 ||
        //        node3 == node4)
        //        return false;
        //    foreach (var neighbor in node1.Neighbors)
        //    {
        //        if (neighbor.Value.Label == node2.Label)
        //        {
        //            findNode2 = true;
        //        }
        //        if (neighbor.Value.Label == node3.Label)
        //        {
        //            findNode3 = true;
        //        }
        //        if (neighbor.Value.Label == node4.Label)
        //        {
        //            findNode4 = true;
        //        }
        //        if (findNode2 && findNode3 && findNode4)
        //            return true;
        //    }
        //    return false;
        //}
        private void ReportProgressFind3Clique(float progress)
        {
            Console.WriteLine(progress);
        }

        private void ReportprogressFind4Clique(float progress)
        {
            Console.WriteLine(progress);
        }

        #endregion Methods
    }

    public class StructureAlgorithm1 : IAlgorithm
    {
        #region Fields (6)

        private int _cliqueSize = 5;
        private int _clusterNumber = 1;
        private int _counterTick;
        private string _path = string.Format(@"c:\temp\Results-{0:d-h-m-s}-continues.txt", DateTime.Now);
        private string _path1 = string.Format(@"c:\temp\Results-{0:d-h-m-s}.txt", DateTime.Now);
        private int _treshold = 4;

        #endregion Fields

        #region Properties (4)

        public int CliqueSize
        {
            get { return _cliqueSize; }
            set { _cliqueSize = value; }
        }

        public string Text { get; set; }

        public int Threshold
        {
            get { return _treshold; }
            set { _treshold = value; }
        }

        public double Treshold
        {
            get { return _treshold; }
            set { _treshold = (int)value; }
        }

        #endregion Properties

        #region Methods (20)

        // Public Methods (7) 
        private void ResetGraph(IGraph graph)
        {
            foreach (GraphNode node in graph.Nodes)
            {
                node.ClusterNumber = 0;
                node.IsMarkedAsDeleted = false;
                node.ThreeCliqueNumber = 0;
                node.TempClusterNumber = 0;
                node.ClusterNumbers = new List<int>();
            }
        }

        public void Run(IGraph graph)
        {
            ResetGraph(graph);
            _path = string.Format(@"c:\temp\{0}{1}-{2}-{3}-continues.txt",
                                  "", //DateTime.Now,
                                  Text.Replace(".txt", ""),
                                  CliqueSize,
                                  Treshold);
            _path1 = string.Format(@"c:\temp\{0}{1}-{2}-{3}.txt",
                                   "", //DateTime.Now,
                                   Text.Replace(".txt", ""),
                                   CliqueSize,
                                   Treshold);


            using (StreamWriter sw = File.AppendText(_path))
            {
                sw.WriteLine("DateTime {0} ,Start Graph {1} ,CliqueSize {2} ,Threshold {3}",
                             DateTime.Now,
                             Text,
                             CliqueSize,
                             Threshold);
            }
            using (StreamWriter sw = File.AppendText(_path1))
            {
                sw.WriteLine("DateTime {0} ,Start Graph {1} ,CliqueSize {2} ,Threshold {3}",
                             DateTime.Now,
                             Text,
                             CliqueSize,
                             Threshold);
            }
            graph.SortGraphByNeighbors();


            InitGraph(graph);
            List<GraphNode> nodes;
            while (FindCliqueInGraph(graph, out nodes, CliqueSize))
            {
                
            }
          //  FindCliqueInGraph(graph, out nodes, CliqueSize);
        }

  
        // Private Methods (13) 

        private void AddNodeToBiggerCluster(int size, SortedDictionary<string, GraphNode> cliqueNodes, GraphNode item,
                                            SortedDictionary<string, SortedDictionary<string, GraphNode>> list2)
        {
            SortedDictionary<string, GraphNode> dict = new SortedDictionary<string, GraphNode>();
            int[] stamp = new int[size];
            int index = 0;

            foreach (KeyValuePair<string, GraphNode> item2 in cliqueNodes)
            {
                stamp[index] = item2.Value.SequenceNumber;
                dict.Add(item2.Key, item2.Value);
                index++;
                //item2.Value.IsMarkedAsDeleted = true;
                //item2.Value.ClusterNumber = clusterNumber;
            }

            stamp[index] = item.SequenceNumber;
            dict.Add(item.Label, item);
            Array.Sort(stamp);
            string key = string.Join(",", stamp);

            if (list2.ContainsKey(key)) //make sure that  duplicate clique not added
            {
                if (FindCommonItems(list2[key], dict).Count > size - 1)
                    return;
            }
            list2.Add(key, dict);
        }

        private bool Containes(IList<GraphNode> outer, List<GraphNode> inner)
        {
            int i = 0;
            List<GraphNode> nodes = new List<GraphNode>();

            foreach (GraphNode outNode in outer)
            {
                //if (outNode.IsMarkedAsDeleted) continue;
                foreach (GraphNode innerNode in inner)
                {
                    if (outNode.Label == innerNode.Label)
                    {
                        nodes.Add(outNode);
                        i++;
                    }
                    if (i != Threshold) continue;
                    if (IsNClique(nodes))
                        return true;
                    i = 0;
                    nodes.Clear();
                }
            }
            return false;
        }

        private void ExpandCluster(List<GraphNode> nodes)
        {
            while (true)
            {
                GraphNode node = ExpandToCluster(nodes);
                if (node != null)
                    nodes.Add(node);
                else
                    break;
            }
        }

        private GraphNode ExpandToCluster(List<GraphNode> nodes)
        {
            foreach (GraphNode a in nodes)
            {
                //if (a.IsMarkedAsDeleted)
                //    continue;
                foreach (GraphNode b in a.Neighbors.Values)
                {
                    //if (b.IsMarkedAsDeleted)
                    //    continue;
                    _counterTick++;
                    if (_counterTick > 100000)
                    {
                        _counterTick = 0;
                        using (StreamWriter sw = File.AppendText(_path))
                        {
                            sw.WriteLine("DateTime {0} ExpandToCluster CounterTick {1} node In cluster {2}",
                                         DateTime.Now,
                                         _clusterNumber,
                                         nodes.Count);
                        }
                    }

                    if (!Containes(b.Neighbors.Values, nodes)) continue;
                    if (nodes.Contains(b)) continue;
                    return b;
                }
            }
            return null;
        }

        private IEnumerable<SortedDictionary<string, GraphNode>> Find3Clique(IEnumerable<GraphNode> graph)
        {
            List<SortedDictionary<string, GraphNode>> lists = new List<SortedDictionary<string, GraphNode>>();
            int cliqueSequnceNumber = 0;

            foreach (GraphNode root in graph)
            {
                //if (root.IsMarkedAsDeleted ||
                //    root.ThreeCliqueNumber != 0)
                //    continue;
                foreach (KeyValuePair<string, GraphNode> neighbor in root.Neighbors)
                {
                    if (/*neighbor.Value.IsMarkedAsDeleted ||*/
                        neighbor.Value.ThreeCliqueNumber != 0)
                        continue;
                    SortedList<string, GraphNode> list = FindCommonItems(root.Neighbors, neighbor.Value.Neighbors);
                    foreach (KeyValuePair<string, GraphNode> item in list)
                    {
                        if (item.Value.ThreeCliqueNumber != 0)
                            continue;
                        cliqueSequnceNumber++;

                        SortedDictionary<string, GraphNode> dic = new SortedDictionary<string, GraphNode>();
                        if (root.Label == neighbor.Key ||
                            root.Label == item.Key ||
                            neighbor.Key == item.Key) continue;

                        cliqueSequnceNumber++;
                        dic.Add(root.Label, root);
                        dic.Add(neighbor.Key, neighbor.Value);
                        dic.Add(item.Key, item.Value);

                        root.ThreeCliqueNumber = cliqueSequnceNumber;
                        neighbor.Value.ThreeCliqueNumber = cliqueSequnceNumber;
                        item.Value.ThreeCliqueNumber = cliqueSequnceNumber;

                        lists.Add(dic);
                    }
                }
            }
            return lists;
        }

        private SortedDictionary<string, SortedDictionary<string, GraphNode>>
            FindBiggerClique(IGraph graph, IEnumerable<SortedDictionary<string, GraphNode>> clique, int size)
        {
            SortedDictionary<string, SortedDictionary<string, GraphNode>> list2 =
                new SortedDictionary<string, SortedDictionary<string, GraphNode>>();
            //  int clusterNumber = 0;
            foreach (SortedDictionary<string, GraphNode> cliqueNodes in clique)
            {
                foreach (GraphNode item in graph.Nodes)
                {
                    //if (item.IsMarkedAsDeleted)
                    //    continue;
                    if (cliqueNodes.ContainsKey(item.Label))
                        continue;

                    List<KeyValuePair<string, GraphNode>> commonElements =
                        item.Neighbors.Intersect(cliqueNodes).ToList();
                    int count = 0;
                    foreach (KeyValuePair<string, GraphNode> item1 in commonElements)
                    {
                       // if (!item1.Value.IsMarkedAsDeleted)
                            count++;
                    }
                    if (count < size - 1)
                        continue;
                    //    if (!Contains(item.Neighbors, cliqueNodes, size - 1)) continue;

                    AddNodeToBiggerCluster(size, cliqueNodes, item, list2);
                    break;
                }
            }
            return list2;
        }

        private bool FindCliqueInGraph(IGraph graph, out List<GraphNode> nodes, int cliqueSize)
        {
            bool found = false;
            nodes = new List<GraphNode>();
            IEnumerable<SortedDictionary<string, GraphNode>> clique3List = Find3Clique(graph.Nodes);
            SortedDictionary<string, SortedDictionary<string, GraphNode>> clique4List;

            clique4List = FindBiggerClique(graph, clique3List, 4);
            for (int i = 5; i < cliqueSize + 1; i++)
            {
                clique4List = FindBiggerClique(graph, clique4List.Values, i);
            }

            foreach (KeyValuePair<string, SortedDictionary<string, GraphNode>> keyValuePair in clique4List)
            {
                nodes.Clear();
                foreach (KeyValuePair<string, GraphNode> node in keyValuePair.Value)
                {
                    nodes.Add(node.Value);
                }
                if (IsAllNodesInSameCluster(nodes)) continue;

                WriteHader();
                ExpandCluster(nodes);
                SetNodeToCluster(nodes);
                _clusterNumber++;
                found = true;
            }

            foreach (var node in graph.Nodes)
            {
                if (node.ClusterNumbers.Count > 2)
                    Console.WriteLine(node.Label);
                if (node.IsMarkedAsDeleted)
                    Console.WriteLine(node.Label);

            }
            nodes = null;
            return found;
        }

        private bool IsAllNodesInSameCluster(List<GraphNode> nodes)
        {
            int i = 0;
            if (nodes.Count < 1)
                return false;
            var node1 = nodes[0];
            if (node1.ClusterNumbers.Count < 2)
                return false;
            foreach (int number in node1.ClusterNumbers)
            {
                i = 0;
                foreach (GraphNode node in nodes)
                {
                    if (node.ClusterNumbers.Contains(number))
                        i++;
                }
                if (nodes.Count == i)
                    return true;
            }
            
            return false;
        }

        private void WriteHader()
        {
            using (StreamWriter sw = File.AppendText(_path1))
            {
                sw.WriteLine("DateTime {0} Find Clique {1}", DateTime.Now, _clusterNumber);
            }
            using (StreamWriter sw = File.AppendText(_path))
            {
                sw.WriteLine("DateTime {0} Find Clique {1}", DateTime.Now, _clusterNumber);
            }
        }

        private Dictionary<string, GraphNode> FindCommonItems(SortedDictionary<string, GraphNode> sortedList1,
                                                              IDictionary<string, GraphNode> sortedList2)
        {
            Dictionary<string, GraphNode> nodes = new Dictionary<string, GraphNode>();
            foreach (KeyValuePair<string, GraphNode> item in sortedList1)
            {
                if (sortedList2.ContainsKey(item.Key))
                {
                    nodes.Add(item.Key, item.Value);
                }
            }
            return nodes;
        }

        private SortedList<string, GraphNode> FindCommonItems(SortedList<string, GraphNode> sortedList1,
                                                              SortedList<string, GraphNode> sortedList2)
        {
            SortedList<string, GraphNode> nodes = new SortedList<string, GraphNode>();
            foreach (KeyValuePair<string, GraphNode> item in sortedList1)
            {
                if (sortedList2.ContainsKey(item.Key)) //&& item.Value.ThreeCliqueNumber != 0)
                {
                    nodes.Add(item.Key, item.Value);
                }
            }
            return nodes;
        }

        private void InitGraph(IGraph graph)
        {
            foreach (GraphNode node in graph.Nodes)
            {
                node.ThreeCliqueNumber = 0;
            }
        }

        private static bool IsNClique(List<GraphNode> nodes)
        {
            nodes.Sort((x, y) => String.Compare(x.Label, y.Label, StringComparison.Ordinal));

            for (int i = 0; i < nodes.Count - 1; i++)
            {
                bool result = false;
                List<bool> found = new List<bool>();
                found.AddRange(Enumerable.Repeat(false, nodes.Count - i - 1));
                int j = 0;

                foreach (GraphNode nodeNeighbor in nodes[i].Neighbors.Values)
                {
                    if (!found[j] && nodes[i + j + 1] == nodeNeighbor)
                    {
                        found[j] = true;
                        j++;
                    }

                    if (!found.All(foundInner => foundInner)) continue;
                    result = true;
                    break;
                }

                if (!result)
                    return false;
            }

            return true;
        }

        private void SetNodeToCluster(List<GraphNode> nodes)
        {
            using (StreamWriter sw = File.AppendText(_path1))
            {
                //sw.WriteLine("DateTime {0} Find Cluster {1} cluster size {2}", DateTime.Now, _clusterNumber,
                //             nodes.Count);
                //sw.WriteLine();

                foreach (GraphNode graphNode in nodes)
                {
                    sw.Write(string.Format("{0}{1}", graphNode.Label, ","));
                    //graphNode.IsMarkedAsDeleted = true;
                    graphNode.ClusterNumber = _clusterNumber;
                    graphNode.ClusterNumbers.Add(_clusterNumber);
                }
                sw.WriteLine();
            }
        }

        #endregion Methods

        #region Parse file

        public static void ParseFile()
        {
            try
            {
                FolderBrowserDialog fd = new FolderBrowserDialog
                {
                    SelectedPath = @"C:\Users\Administrator\Documents\Results"
                };
                fd.ShowDialog();
                string[] oDirectories = Directory.GetFiles(fd.SelectedPath, "*.txt", SearchOption.AllDirectories);

                foreach (string oDirectory in oDirectories)
                {
                    try
                    {
                        ParseFile(oDirectory);
                    }
                    catch (Exception ex)
                    {
                        Console.WriteLine(ex.Message);
                    }
                }
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
            }
        }

        private static void ParseFile(string p)
        {
            string allFile = File.ReadAllText(p);

            string[] splitedFile = allFile.Split(' ');
            List<string> splitedItems = new List<string>();
            for (int i = 0; i < splitedFile.Length; i++)
            {
                if (splitedFile[i] == "cluster" && splitedFile[i + 1] == "size")
                {
                    splitedItems.Add(splitedFile[i + 2]);
                }
            }

            int count = splitedItems.Count;

            List<string> firstItem = new List<string>();
            List<int> secoundItem = new List<int>();
            int value;
            foreach (string item in splitedItems)
            {
                string[] temp = item.Split(Environment.NewLine.ToCharArray());
                {
                    int.TryParse(temp[0], out value);
                    string[] sss = temp[4].Split(',');
                    Array.Sort(sss);
                    firstItem.Add(string.Join(",", sss));
                    secoundItem.Add(value);
                }
            }
            string s5;
            int t1;
            for (int i = 0; i < secoundItem.Count; i++)
            {
                for (int j = 0; j < secoundItem.Count; j++)
                {
                    if (secoundItem[i] <= secoundItem[j]) continue;
                    t1 = secoundItem[j];
                    secoundItem[j] = secoundItem[i];
                    secoundItem[i] = t1;

                    s5 = firstItem[j];
                    firstItem[j] = firstItem[i];
                    firstItem[i] = s5;
                }
            }


            List<string> results = new List<string>();

            for (int i = 0; i < secoundItem.Count; i++)
            {
                results.Add(secoundItem[i] + "," + firstItem[i]);
            }


            //need to sort strings
            string dir = Path.GetDirectoryName(p);
            string fileName = Path.GetFileNameWithoutExtension(p);
            if (dir == null) return;
            string filePath = Path.Combine(dir, fileName + "-" + count + "new.csv");
            File.WriteAllLines(filePath, results);
        }

        private static void CompareFiles(string filePath1, string filePath2)
        {
            StringBuilder sb = new StringBuilder();
            string filePathrReader1 = File.ReadAllText(filePath1);
            string filePathrReader2 = File.ReadAllText(filePath2);
            string[] allLines1 = filePathrReader1.Split(Environment.NewLine.ToCharArray());
            string[] allLines2 = filePathrReader2.Split(Environment.NewLine.ToCharArray());
            //=new string[1]; allLines2[0] = ",," +
            //  "A3KFJ3, B0LPE8, B0LPF3, B2RZG3, B5BU57, D3DNE3, D3DWA0, E1P5V4, O60674, P00519-2, P00533, P01133, P05231, P06239, P06241, P0961, P12931, P27986, P29350, P29353, P29597, P40763, P42336, P43405, P62993, P62993-2, Q05397, Q06124";
            int length1 = allLines1.Length;
            int length2 = allLines2.Length;
            string[] splitedValues1;
            string[] splitedValues2;
            sb.AppendLine("Cluster number1,Cluster Count 1,Cluster number2,Cluster count 2,Common Nodes,Nodes");
            List<List<string>> common = new List<List<string>>();
            for (int i = 0; i < length1; i++)
            {
                for (int j = 0; j < length2; j++)
                {
                    splitedValues1 = allLines1[i].Split(',');
                    if (splitedValues1.Length < 2) continue;
                    splitedValues1 = splitedValues1.SubArray(2, splitedValues1.Length - 2);
                    splitedValues2 = allLines2[j].Split(',');
                    if (splitedValues2.Length < 2) continue;
                    splitedValues2 = splitedValues2.SubArray(2, splitedValues2.Length - 2);
                    IEnumerable<string> commonList = splitedValues1.Intersect(splitedValues2);
                    IEnumerable<string> enumerable = commonList as string[] ?? commonList.ToArray();
                    int len1 = enumerable.Count();

                    if (enumerable.Count() <= 1) continue;
                    common.Add(new List<string>(enumerable.ToArray()));
                    sb.AppendLine(string.Format("{0},{1},{2},{3},{4},{5}",
                                                i,
                                                splitedValues1.Length,
                                                j,
                                                splitedValues2.Length,
                                                len1,
                                                string.Join(",", enumerable.ToArray())));
                }
            }
            string dir = Path.GetDirectoryName(filePath1);
            string p1 = Path.GetFileNameWithoutExtension(filePath1);
            if (p1 == null) return;
            string fileName1 = p1.Substring(0, p1.Length - 6);
            string p2 = Path.GetFileNameWithoutExtension(filePath2);
            if (p2 == null) return;
            string fileName2 = p2.Substring(0, p2.Length - 6);
            if (dir == null) return;
            string filePath = Path.Combine(dir, "CommonItems-" + fileName1 + "--" + fileName2 + ".csv");
            File.WriteAllText(filePath, sb.ToString());
        }

        public static void CompareFiles()
        {
            try
            {
                string filePath1;
                string filePath2;
                using (OpenFileDialog fd = new OpenFileDialog())
                {
                    fd.InitialDirectory = @"C:\Users\Administrator\Documents\Results";
                    fd.Title = "Select first file to compare";
                    if (fd.ShowDialog() != DialogResult.OK)
                        return;
                    filePath1 = fd.FileName;
                }
                using (OpenFileDialog fd = new OpenFileDialog())
                {
                    fd.InitialDirectory = Path.GetDirectoryName(filePath1);
                    fd.Title = "Select secound file to compare";
                    if (fd.ShowDialog() != DialogResult.OK)
                        return;
                    filePath2 = fd.FileName;
                }
                CompareFiles(filePath1, filePath2);
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
            }
        }

        #endregion parse file
    }
}